People make all kinds of informal drawings as pictorial notations, from quickly encircling objects of interest to sketching details in scenes, designs, and concept proposals. Descriptive drawings of events and situations may be choreographed as complexes of linear motion paths. Patterns of animal migration or movements of hurricanes are shown and compared through clusters of such lines of movement.
Computing devices increasingly are used to track motions, whether in pen based graphic devices responding to stylus movements or in process monitoring equipment where motion data may be calculated from a complex field of events. Such linear motion analyzers can range from relatively simple hand-held Personal Digital Assistants (PDAs) to large and complex arrays of motion detectors, cameras, and other specialized equipment communicating across computer-mediated networks.
As used herein, glyph means a line drawing or other linear configuration that communicates specific relationships or details as structural factors of the motion paths constituting the configuration itself. It is important to distinguish between the schematic configuration of motion paths and the rendered image of a glyph. Even in simple line drawings the marks laid down by a pen or other implement may vary widely. For instance the characteristic imprint of a given type of implement may result in lines that are extremely broad or very narrow. Or the implement may respond to varying pressure, as with a lettering brush or angled calligraphy pen. Or the moving implement may be bounced along its path to draw dots and dashes instead of a solid line. All of these and other variations may be emulated in a computer graphic input system such that variations in the marks rendering various configurations may confuse and obscure similarities in their underlying pattern of motion paths. During comparison of drawn configurations such incidental mark variations can obscure strong similarities of line path disposition and consequently hinder interpretive methods that are dependent solely upon analysis of sets of local mark features.
Because they are so widely evident in human enterprise, glyphs have great potential for user interfaces in such computer-mediated tasks as pictorially searching image databases and guiding computer controlled processes by means of glyph-structured gestures.
To exploit glyphs in a computing environment requires a method of sorting, comparing, and grouping them in terms of their qualitative features. Evaluating structural similarities among a varied collection of glyphs is fundamental to using them as representative tokens of external entities, as data keys for accomplishing pictorial searches of image databases, or as elements of interface control. Comparison of glyph structures is a necessary part of extracting useful pictorial information from their configurations.
Many different techniques have been devised to use glyphs as part of graphic user interfaces of computer systems to enable direct input of pictorial information and to graphically designate search keys for retrieving items from image databases. To the extent that these and other applications rely upon matching local representational features of visual media with specific conceptual content they may be treated as content-centered search keys, whether in textual, pictorial or other media context.
In the earliest databases image features were described by text synopses so that data operations could be directed in terms of keywords and phrases found in the reference text. Such high-level conceptual content keying introduces ambiguities throughout creation, maintenance, and use of textually keyed databases since there is a need to analyze and interpret pictorial content in terms of a common repertoire adequate to the domain of intended use. For example, an architect probably uses quite different keywords for a database of buildings and structures in a city than those relevant to a military tactician or a social historian. As computing systems gained graphic user interfaces, icons that could be activated by a pointing device such as a mouse, stylus, or trackball displaced keyboard commands. But the fundamental dependence upon retrieval by content features has persisted even into pervasively graphic control systems. Whether searching for key words or for key assemblies of local pictorial elements the same problem persists: where the size of the database is large and each item is a complex structure, the processing cost of exhaustively comparing every member with a key is prohibitive. Some means is needed of low-level structural filtering to quickly eliminate unqualified pretenders and to extract a collection of highly likely match candidates that subsequently can be processed in terms of high-level content based parameters.
Existing drawn figure and handwriting recognition devices typically use a template repertoire of local mark features against which to compare and match manually drawn gestural strokes. For each cluster of input lines interpretive software attempts to determine the presence or absence of known features such as lines extending below a baseline; proximity and connection of angles, curves, straight line segments; and closed loops with protruding line extensions. Each input configuration is tested against such template features to arrive at match candidates. Further processing of contextual information may be made to disambiguate matching probabilities, to interpret, and finally to display the recognized characters or word. Graphic interfaces sometimes isolate and compare geometric features of simple shapes to decipher and characterize circles, ellipses, squares, rectangles, triangles, and even free-form shapes drawn by hand.
Current approaches to interpreting linear gestures generally depend upon one or more of the following approaches to processing local mark feature sets:
derivation of correlation factors from scalar multiplication of vectors representing stroke path segments that are then compared with stored scalar products of template configurations; PA1 isolation of geographical features such as lagoons (closed areas) and bays (open areas) along with directional mark features such as loops, arcs or straight segments found among clustered line strokes that are compared with stored template features; PA1 circumnavigation of the peripheries of a cluster, comparing parameters of height, width, perimeter, area, and waveform with those of stored templates; PA1 manipulation, normalization, and comparison of pen strokes with stored template gesture prototypes; and PA1 classification of shapes by first discerning features such as blockiness, symmetry, convexity, and count of edge-breakthroughs and then calculating by linear transform a parameterized shape class value. PA1 Effectiveness of discrimination and matching among candidates is an inverse function of the ambiguity of feature set articulation. The efficiency of any method based on feature matching decreases as the reference repertoire increases in size and variability of its members. PA1 Characterizations of non-textual configurations depend upon formal definitions of geometric features and are difficult to categorize and rank if they vary much from simple geometric figures. PA1 Storing, searching, comparing, and retrieving items of large glyph databases are typically slow and computationally expensive. PA1 Current feature matching methods are not easily extensible to new feature sets, thereby discouraging use of glyph structure sets to provide user customized computing device interfaces. PA1 (a) a template analytic lattice constituted of a predetermined multiplicity of cell partitions, the totality of the analytic lattice being coextensive with the defined rendering area of the glyph and in the plane of motion of the linear motion paths of the glyph; PA1 (b) means of interpreting each linear motion path as a sequence of displacement vectors, determining which displacement vectors intersect specific boundaries of specific cells of the analytic lattice, and registering each cell boundary intersection by both recording the intersecting vector inclination gradient and incrementing an associated vector count for each cell bounded by the intersected boundary; PA1 (c) means of combining all of the vector inclination gradients registered for each the cell thereby to produce an associated numeric clutch value as a cumulative total of the registered vector inclination gradients; and PA1 (d) means of deriving a numeric inclination index value for each cell from the associated vector count and the associated clutch value, the kind of the inclination index being selected from a group comprising PA1 to provide a widely applicable and indefinitely extensible method of analyzing, comparing, sorting, and classifying glyphs in terms of periodic structural characteristics of their respective motion path configurations; PA1 to provide a simple and coherent system of nomenclature for representing periodic structural relationships among items of a glyph data set and for comparing such periodic structural relationships within a variably definable range of match criteria; PA1 to provide a straightforward means by which computing devices may manipulate and communicate comparative data regarding glyph linear configurations using conventional alphanumeric operations; PA1 to provide a means by which the interface of a computing, game, entertainment, or other device may be variously customized by its user and be thereby controlled in accordance with unique configurations of linear movement effected by the user; and PA1 to provide a means of variably eliciting computer interface control elements by explicitly associating them, within variable and graduated ranges of criteria, with periodic values derived from either manual or automated tracings of the disposition of constituents of an image or other patterned deployment within some defined area of a plane.
Whether a computer interface is based on entering text by keyboard, pointing and clicking icons with a mouse, or marking a touch sensitive surface with a stylus, there are a number of disadvantages inherent in any comparative control system based upon a template repertoire of local mark features:
A list of prior patents currently known to applicant in connection with this matter, at least some of which may be of interest, is provided below:
With respect to the "SPOT System" referred to herein, applicant authored an article on this approach entitled "The SPOT System: A Method of Numerically Specifying Spatial Configurations" published in ACM/SIGGRAPH Computer Graphics of April, 1981.